第十章复习题20200111

第十章复习题 20200111

真的错题

42

在归并排序中，若待排序记录的个数为 20，则共需要进行 () 趟归并。

（0.7 分）

0.0分

• A、
  [8](javascript:void(0);)
• B、
  [4](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [5](javascript:void(0);)
  我的答案：D

正确答案：未知

10->5->3->2->1 一共五次。

63

设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行的最小交换次数是 ()。（0.7 分）

0.0分

• A、
  [20](javascript:void(0);)
• B、
  [8](javascript:void(0);)
• C、
  [6](javascript:void(0);)
• D、
  [7](javascript:void(0);)
  我的答案：A

正确答案：C

我觉得这是个错题。第四个和第八个、第一个和第二个、第一个和第六个、第三个和第七个、第五个和第七个。一共 5 次

67

在归并排序中，若待排序记录的个数为 20，则共需要进行 5 趟归并，在第 3 趟归并中，是把长度为 4 的有序表归并为长度为 () 的有序表。

（0.7 分）

0.0分

• A、
  [7](javascript:void(0);)
• B、
  [4](javascript:void(0);)
• C、
  [5](javascript:void(0);)
• D、
  [8](javascript:void(0);)
  我的答案：D

搜题答案：B，百度 D

错题，很明显是 D 啊
2021 年 1 月 11 日
15:28

我的错题

9

在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（）。

（0.7 分）

0.0分

• A、
  [O(1)](javascript:void(0);)
• B、
  [O(n)](javascript:void(0);)
• C、
  
• D、
  

我的答案：B

正确答案：A

堆排序不需要过多附加空间

23

在对一组记录（50，35，95，25，15，70，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置至少需比较 ().次。

（0.7 分）

0.0分

• A、
  [3](javascript:void(0);)
• B、
  [6](javascript:void(0);)
• C、
  [4](javascript:void(0);)
• D、
  [5](javascript:void(0);)
  我的答案：D

正确：A，

从有序表后面开始向前找

40

快速排序在 () 情况下最易发挥其长处。（0.7 分）

0.0分

• A、
  [被排序的数据中最大值与最小值相差不大](javascript:void(0);)
• B、
  [被排序的数据量很大](javascript:void(0);)
• C、
  [被排序的数据已基本有序](javascript:void(0);)
• D、
  [被排序的数据完全无序](javascript:void(0);)
  我的答案：B

正确：D

很明显完全无序对快速排序最友好

42

在归并排序中，若待排序记录的个数为 20，则共需要进行 () 趟归并。

（0.7 分）

0.0分

• A、
  [8](javascript:void(0);)
• B、
  [4](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [5](javascript:void(0);)
  我的答案：D

正确答案：百度说 D

10->5->3->2->1，一共 5 躺

43

堆的形状是一棵（）。（0.7 分）

0.0分

• A、
  [满二叉树](javascript:void(0);)
• B、
  [完全二叉树](javascript:void(0);)
• C、
  [二叉排序树](javascript:void(0);)
• D、
  [平衡二叉树](javascript:void(0);)
  我的答案：D

正确答案：B

堆是完全二叉树

48

在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ()。

（0.7 分）

0.0分

• A、
  [先快速排序然后堆排序](javascript:void(0);)
• B、
  [快速排序](javascript:void(0);)
• C、
  [堆排序](javascript:void(0);)
• D、
  [先堆排序然后快速排序](javascript:void(0);)
  我的答案：A

正确答案：C

快排在有序序列分块根本就分不开，一直找边上的值

53

快速排序方法在（）情况下最不利于发挥其长处。（0.7 分）

0.0分

• A、
  [要排序的数据中有多个相同值](javascript:void(0);)
• B、
  [要排序的数据量太大](javascript:void(0);)
• C、
  [要排序的数据个数为奇数](javascript:void(0);)
• D、
  [要排序的数据已基本有序](javascript:void(0);)
  我的答案：A

正确：D

61

若对一组记录（46，79，56，38，40，80，35，50，74）进行直接选择排序，用 k 表示最小值元素的下标，进行第一趟时 k 的初值为 1，则在第一趟选择最小值的过程中，k 的值被修改 () 次。（0.7 分）

0.0分

• A、
  [5](javascript:void(0);)
• B、
  [4](javascript:void(0);)
• C、
  [3](javascript:void(0);)
• D、
  [2](javascript:void(0);)
  我的答案：C

正确答案：D

因为这个题把 46 下标当成 1 了。沙比提

63

设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行的最小交换次数是 ()。（0.7 分）

0.0分

• A、
  [20](javascript:void(0);)
• B、
  [8](javascript:void(0);)
• C、
  [6](javascript:void(0);)
• D、
  [7](javascript:void(0);)
  我的答案：A

搜题答案：C

我觉得这是个错题。第四个和第八个、第一个和第二个、第一个和第六个、第三个和第七个、第五个和第七个。一共 5 次

67

在归并排序中，若待排序记录的个数为 20，则共需要进行 5 趟归并，在第 3 趟归并中，是把长度为 4 的有序表归并为长度为 () 的有序表。

（0.7 分）

0.0分

• A、
  [7](javascript:void(0);)
• B、
  [4](javascript:void(0);)
• C、
  [5](javascript:void(0);)
• D、
  [8](javascript:void(0);)
  我的答案：D

搜题答案：B

错题，很明显是 D 啊

69

已知一个链表中有 3000 个结点，每个结点存放一个整数，（）可用于解决这 3000 个整数的排序问题且不需要对算法作大的变动。

（0.7 分）

0.0分

• A、
  [简单选择排序方法](javascript:void(0);)
• B、
  [堆排序方法](javascript:void(0);)
• C、
  [直接插入排序法](javascript:void(0);)
• D、
  [快速排序方法](javascript:void(0);)
  我的答案：D

正确答案：B

因为快速排序基于链表没办法逆向查找。

76

快速排序在（）情况下最不利于发挥其长处。（0.7 分）

0.0分

• A、
  [被排序的数据中最大值与最小值相差不大](javascript:void(0);)
• B、
  [被排序的数据已基本有序](javascript:void(0);)
• C、
  [被排序的数据完全无序](javascript:void(0);)
• D、
  [被排序的数据量很大](javascript:void(0);)
  我的答案：A

正确答案：B

77

在堆排序，快速排序和归并排序中，若只从存储空间考虑，则空间效率最差的事（）方法

（0.7 分）

0.0分

• A、
  [都一样](javascript:void(0);)
• B、
  [归并排序](javascript:void(0);)
• C、
  [堆排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  我的答案：D

正确答案：B

归并排序 On

79

在堆排序过程中，由 n 个待排序的记录建成初始堆需要（）次筛选；

（0.7 分）

0.0分

• A、
  [n](javascript:void(0);)
• B、
  [n-1](javascript:void(0);)
• C、
  [n/2](javascript:void(0);)
• D、
  

我的答案：A

正确答案：C

因为非结点和叶子节点个数差不多，只用对非叶子结点进行筛选

108

从时间上看，快速排序的平均性能好于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归，若每趟快速排序都将记录序列均匀地分割成为长度相接近的两个子序列，则栈的最大深度（含最外层也进栈）为

；如果每次先对较短的子序列进行快速排序，所需要的附加空间为（）。

（0.7 分）

0.0分

• A、
  [O（n）](javascript:void(0);)
• B、
  
• C、
  
• D、
  [log2n+1](javascript:void(0);)
  我的答案：A

正确答案：C

百度原题：从时间上看，快速排序的平均性能好于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归，若每一趟快速排序都将记录序列均匀地分割成长度相接近的两个序列，则栈的最大深度（含最外层也进栈）为＿＿log2n 下取整 +1＿＿＿＿；在最坏情况下，栈的深度为＿＿＿n＿＿＿；如果每次先对较短的子序列进行快速排序，则栈的最大深度降为＿＿＿log2n＿＿＿；所需要的附加空间为＿＿＿log2n＿＿＿。

网友 1：

是这样的,

优先对较短的排序,

会减少压栈空间.

记得应该是最坏的可能是 logn 层.

以稍微长一点的程序减少堆栈的使用.

在数据很多时比较好.

网友 2：

所以应该是用了尾递归，把长的那部分不用递归，用循环表示

这样最坏的栈深度是 lgn，普通的递归最坏是 n 的

网友 3：

弱弱地问一下，

如果这样的话，全部用循环不是更好吗？

网友 4：

有一点点作用把，总是从较短的一半开始的话，期望上就能较快的返回。

假设每次都正好划分在 1/3 处的话，从小的一边开始，那么 log（3）N 次递归以后，就开始返回了。

不过长的一边也要处理才行，貌似到时候栈的使用还是很多的……

对了！尾递归！

michael122 正解！！

128

设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用（）排序法。

（0.7 分）

0.0分

• A、
  [冒泡排序](javascript:void(0);)
• B、
  [基数排序](javascript:void(0);)
• C、
  [堆排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  我的答案：A

正确答案：C

堆排序！！

138

假定一组记录为（46，79，56，64，38，40，84，43），在冒泡排序的过程中进行第一趟排序时，元素 79 将最终下沉到其后第 () 个元素的位置。（0.7 分）

0.0分

• A、
  [4](javascript:void(0);)
• B、
  [6](javascript:void(0);)
• C、
  [3](javascript:void(0);)
• D、
  [5](javascript:void(0);)
  我的答案：B

正确答案：A

是其后！！！！！注意啦

139

一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。

（0.7 分）

0.0分

• A、
  [希尔排序](javascript:void(0);)
• B、
  [快速排序](javascript:void(0);)
• C、
  [冒泡排序](javascript:void(0);)
• D、
  [堆排序](javascript:void(0);)
  我的答案：B

正确答案：A

堆排序可以把最大或最小放在堆顶

快排的基准放在了最终位置

冒泡不用多说

做题不确定

1

以下说法错误的是 ()

（0.7 分）

• A、
  [树形结构可以表达(组织)更复杂的数据](javascript:void(0);)
• B、
  [线性结构中的一个结点至多只有一个直接后继](javascript:void(0);)
• C、
  [线性结构中的一个结点至少只有一个直接后继](javascript:void(0);)
• D、
  [树(及一切树形结构)是一种"分支层次"结构](javascript:void(0);)
  C。这个 A、D 不确定

2

快速排序的记录移动次数（）比较次数，其总执行时间为 O(nlog2n)。（0.7 分）

• A、
  [大于](javascript:void(0);)
• B、
  [大于等于](javascript:void(0);)
• C、
  [小于](javascript:void(0);)
• D、
  [小于等于](javascript:void(0);)
  D，小于等于，你给我记住了，有可能每一次比较都要换，也有可能比较之后不换

在快速排序中，每次比较后才移动记录，但有时候不需要移动记录，因此，快速排序的记录移动次数不大于比较的次数。但如果记录移动次数等于比较的次数，说明每次比较都要移动记录，是快速排序最坏的情况，在此情况下执行时间为 O(n²)。

4

设有 1024 个无序的元素，希望用最快的速度挑选出其中前 5 个最大的元素，最好选用（

（0.7 分）

• A、
  [冒泡排序](javascript:void(0);)
• B、
  [快速排序](javascript:void(0);)
• C、
  [堆排序](javascript:void(0);)
• D、
  [选择排序](javascript:void(0);)
  C。堆排序怎么说也比选择排序快吧

7

在归并排序过程中，需归并的趟数为 ()。

（0.7 分）

• A、
  
• B、
  [n](javascript:void(0);)
• C、
  
• D、
  [n-1](javascript:void(0);)
  A，相同大小进行归并就是一趟，每趟基本上组数除以 2

8

对有 n 个记录的表作快速排序，在最坏情况下，算法的时间复杂度是

（0.7 分）

• A、
  
• B、
  
• C、
  
• D、
  [O(n)](javascript:void(0);)
  A。快速最坏时间 O(n^2)，最坏空间 O(n)

9

在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（）。

（0.7 分）

• A、
  [O(1)](javascript:void(0);)
• B、
  [O(n)](javascript:void(0);)
• C、
  
• D、
  

B，第一次构建一个堆

10

在所有的排序方法中，关键字的比较次数与记录的初始排列无关的是 ()

（0.7 分）

• A、
  [冒泡排序](javascript:void(0);)
• B、
  [堆排序](javascript:void(0);)
• C、
  [直接插入排序](javascript:void(0);)
• D、
  [直接选择排序](javascript:void(0);)
  D，感觉是 D，其实感觉 A 也是

11

设一组初始记录关键字序列为 (45，80，55，40，42，85)，则以第一个记录关键字 45 为基准而得到一趟快速排序的结果是（）。（0.7 分）

• A、
  [42，40，45，80，85，88](javascript:void(0);)
• B、
  [42，40，45，85，55，80](javascript:void(0);)
• C、
  [40，42，45，55，80，83](javascript:void(0);)
• D、
  [42，40，45，55，80，85](javascript:void(0);)
  D。45 为基准

45，80，55，40，42，85 找到 42<45，80>45

42，45，55，40，80，85 找到 40<45，55>45

42， 40，45，55，80，85

12

设需要对 5 个不同的记录关键字进行排序，至多需要比较（）次。（0.7 分）

• A、
  [12](javascript:void(0);)
• B、
  [9](javascript:void(0);)
• C、
  [10](javascript:void(0);)
• D、
  [11](javascript:void(0);)
  C。百度：首先随 i 便选择一个数为基数，再选择一个数和比较就是 1 次，选择第三个数最多比较 2 次就可属以属确定它的位置，选择第四个数最多比较 3 次也就能够确定它的位置，最后一个数最多比较 4 次同样可以确定它的位置了。1+2+3+4=10。

13

在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是稳定的有 ()。

（0.7 分）

• A、
  [快速排序](javascript:void(0);)
• B、
  [选择排序](javascript:void(0);)
• C、
  [希尔排序](javascript:void(0);)
• D、
  [插入排序](javascript:void(0);)
  D。插入排序稳定，不稳定的只有希尔排序、快速排序、简单选择排序、堆排序

18

在归并排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是稳定的有 ()。

（0.7 分）

• A、
  [归并排序](javascript:void(0);)
• B、
  [选择排序](javascript:void(0);)
• C、
  [希尔排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  A。归并稳定

19

二路归并排序的时间复杂度为（）。

（0.7 分）

• A、
  [O(n)](javascript:void(0);)
• B、
  
• C、
  
• D、
  

B。二路归并时间复杂度 nlog2n

21

设一组初始记录关键字序列为 (9，8，7，6，5，4，3，2，1，0)，则以增量 d=5 的一趟希尔排序结束后前 5 条记录关键字为（）。（0.7 分）

• A、
  [0，3，2，4，1](javascript:void(0);)
• B、
  [4，2，3，1，0](javascript:void(0);)
• C、
  [4，3，2，1，0](javascript:void(0);)
• D、
  [0，1，2，3，4](javascript:void(0);)
  C，先分五组，然后每组分别进行插入排序，分别是[0,d],[1,d+1],[2,d+2],[3,d+3],[4,d+4] 排好后再分组再排，但每一次组数要变少，直到最后只有 1 组

22

用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：

25，84，21，47，15，27，68，35，20

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84

15，20，21，25，27，35，47，68，84

采用的排序方法是（）。

（0.7 分）

• A、
  [选择排序](javascript:void(0);)
• B、
  [归并排序](javascript:void(0);)
• C、
  [希尔排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  D。快速排序太难了，一次得排完才行，我还不会归并排序

23

在对一组记录（50，35，95，25，15，70，60，45，83）进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置至少需比较 ().次。

（0.7 分）

• A、
  [3](javascript:void(0);)
• B、
  [6](javascript:void(0);)
• C、
  [4](javascript:void(0);)
• D、
  [5](javascript:void(0);)
  D，注意比较次数，加上和 70 比小了。

24

对 n 个元素的序列进行冒泡排序，最少的比较次数是 ()。（0.7 分）

• A、
  [n-1](javascript:void(0);)
• B、
  [n/2](javascript:void(0);)
• C、
  [n](javascript:void(0);)
• D、
  [（n-1）/2](javascript:void(0);)
  A。指改进的冒泡排序，气泡但不交换

25

一组记录的关键字为（45，80，55，40，42，85），则利用快速排序的方法，以第 1 个记录为基准得到一次划分结果是（）。（0.7 分）

• A、
  [(42,40,45,55,80,85)](javascript:void(0);)
• B、
  [(42,40,45,80,55,85)](javascript:void(0);)
• C、
  [(42,40,45,85,55,80)](javascript:void(0);)
• D、
  [(40,42,45,55,80,85)](javascript:void(0);)
  A，位置越靠前的比他大的，交换后越靠后，位置越靠后的比他小的，交换后越靠前，且他们一对一对的。

27

在平均情况下，快速排序时间复杂性为

，空间复杂性为（）；

（0.7 分）

• A、
  
• B、
  
• C、
  [O（n）](javascript:void(0);)
• D、
  

D。因为需要栈进行递归调用

28

从未排序序列中依次取出元素与已排序序列中的元素做比较，将其放入已排序序列中的正确位置上，此方法称为（）。

（0.7 分）

• A、
  [交换排序](javascript:void(0);)
• B、
  [插入排序](javascript:void(0);)
• C、
  [归并排序](javascript:void(0);)
• D、
  [选择排序](javascript:void(0);)
  B。

31

对于直接插入排序、冒泡排序、简单选择排序、堆排序、快速排序，当文件“局部有序”或文件长度较小的情况下，最佳的内部排序方法是（）。

（0.7 分）

• A、
  [直接插入排序](javascript:void(0);)
• B、
  [堆排序](javascript:void(0);)
• C、
  [冒泡排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  A，不确定

32

一组记录的关键字为（25，50，15，35，80，85，20，40，36，70），其中含有 5 个长度为 2 的有序表，用归并排序方法对该序列进行一趟归并后的结果为 ()。

（0.7 分）

• A、
  [15,25,35,50,80,20,85,40,70,36](javascript:void(0);)
• B、
  [15,25,35,50,80,20,36,40,70,85](javascript:void(0);)
• C、
  [15,25,50,35,80,85,20,36,40,70](javascript:void(0);)
• D、
  [15,25,35,50,20,40,80,85,36,70](javascript:void(0);)
  D。归并排序，第一趟结果应该是一对对的有序，但这题已知是 5 个长度为 2 的有序表，因此第一趟就变成 442 了。

33

在所有的排序方法中，关键字的比较次数与记录的初始排列无关的是 ()

（0.7 分）

• A、
  [直接选择排序](javascript:void(0);)
• B、
  [直接插入排序](javascript:void(0);)
• C、
  [冒泡排序](javascript:void(0);)
• D、
  [shell排序](javascript:void(0);)
  A。但我觉得什么排序比较次数都是一定的。

34

直接插入排序和冒泡排序的时间复杂性为

,若初始数据有序（即正序），则时间复杂性为 ()。

（0.7 分）

• A、
  
• B、
  [O（n）](javascript:void(0);)
• C、
  
• D、
  

B。

37

堆是一种 () 排序。（0.7 分）

• A、
  [归并](javascript:void(0);)
• B、
  [选择](javascript:void(0);)
• C、
  [插入](javascript:void(0);)
• D、
  [交换](javascript:void(0);)
  B。堆是一种选择排序

38

排序的目的是为了以后对已排序的数据元数进行（）操作。（0.7 分）

• A、
  [合并](javascript:void(0);)
• B、
  [打印输出](javascript:void(0);)
• C、
  [分类](javascript:void(0);)
• D、
  [查找](javascript:void(0);)
  D，但是不一定

40

快速排序在 () 情况下最易发挥其长处。（0.7 分）

• A、
  [被排序的数据中最大值与最小值相差不大](javascript:void(0);)
• B、
  [被排序的数据量很大](javascript:void(0);)
• C、
  [被排序的数据已基本有序](javascript:void(0);)
• D、
  [被排序的数据完全无序](javascript:void(0);)
  B，但是我不确定，我感觉 C 也有一定道理，但是基本有序适合直接插入排序

41

希尔排序的增量序列必须是（）。（0.7 分）

• A、
  [递减的](javascript:void(0);)
• B、
  [非递减的](javascript:void(0);)
• C、
  [随机的](javascript:void(0);)
• D、
  [递增的](javascript:void(0);)
  A。必须是递减的

42

在归并排序中，若待排序记录的个数为 20，则共需要进行 () 趟归并。

（0.7 分）

• A、
  [8](javascript:void(0);)
• B、
  [4](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [5](javascript:void(0);)
  D。22 配对算一趟。

43

堆的形状是一棵（）。（0.7 分）

• A、
  [满二叉树](javascript:void(0);)
• B、
  [完全二叉树](javascript:void(0);)
• C、
  [二叉排序树](javascript:void(0);)
• D、
  [平衡二叉树](javascript:void(0);)

D。我猜。

44

在堆排序过程中，由 n 个待排序的记录建成堆；在每次筛选运算的过程中，记录的比较和移动次数的数量级为 ()。

（0.7 分）

• A、
  
• B、
  
• C、
  [O（n）](javascript:void(0);)
• D、
  

B。要进行 n 次筛选，因此是 log

47

冒泡排序、简单选择排序、堆排序、快速排序，快速排序在最坏情况下时间复杂性是

,比（）排序性能差。

（0.7 分）

• A、
  [快速排序](javascript:void(0);)
• B、
  [堆排序](javascript:void(0);)
• C、
  [直接插入排序](javascript:void(0);)
• D、
  [冒泡排序](javascript:void(0);)
  B。堆排序最坏也是 nlogn

48

在堆排序和快速排序中，若原始记录接近正序或反序，则选用 ()。

（0.7 分）

• A、
  [先快速排序然后堆排序](javascript:void(0);)
• B、
  [快速排序](javascript:void(0);)
• C、
  [堆排序](javascript:void(0);)
• D、
  [先堆排序然后快速排序](javascript:void(0);)
  A。交换排序和选择排序的区别

50

在下述排序算法中，平均速度最快的是（）。

（0.7 分）

• A、
  [堆排序](javascript:void(0);)
• B、
  [归并排序](javascript:void(0);)
• C、
  [归并排序和堆排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  D。我爱快排，我不管了

51

若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（）次比较。（0.7 分）

• A、
  [91](javascript:void(0);)
• B、
  [33](javascript:void(0);)
• C、
  [70](javascript:void(0);)
• D、
  [45](javascript:void(0);)
  A。（1+13）*13/2

52

利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。

（0.7 分）

• A、
  [O(n)](javascript:void(0);)
• B、
  
• C、
  
• D、
  

D。

53

快速排序方法在（）情况下最不利于发挥其长处。（0.7 分）

• A、
  [要排序的数据中有多个相同值](javascript:void(0);)
• B、
  [要排序的数据量太大](javascript:void(0);)
• C、
  [要排序的数据个数为奇数](javascript:void(0);)
• D、
  [要排序的数据已基本有序](javascript:void(0);)
• A，不确定

57

对 n 个元素的序列进行冒泡排序，其比较次数为 n（n-1）/2 时，其原始数据序列是（）情况。（0.7 分）

• A、
  [降序](javascript:void(0);)
• B、
  [无序](javascript:void(0);)
• C、
  [块内无序，块间有序](javascript:void(0);)
• D、
  [升序](javascript:void(0);)
  A。实际上是气泡到了最后一轮就可以，应该没必要完全逆序

59

对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 ()。（0.7 分）

• A、
  [n+1](javascript:void(0);)
• B、
  [n-1](javascript:void(0);)
• C、
  [n](javascript:void(0);)
• D、
  [n(n-1)/2](javascript:void(0);)
  D。（1+n-1）（n-1）/2

61

若对一组记录（46，79，56，38，40，80，35，50，74）进行直接选择排序，用 k 表示最小值元素的下标，进行第一趟时 k 的初值为 1，则在第一趟选择最小值的过程中，k 的值被修改 () 次。（0.7 分）

• A、
  [5](javascript:void(0);)
• B、
  [4](javascript:void(0);)
• C、
  [3](javascript:void(0);)
• D、
  [2](javascript:void(0);)
  C，但 k 初值为 1，是不是写错了？k 应该是 0 吧

63

设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行的最小交换次数是 ()。（0.7 分）

• A、
  [20](javascript:void(0);)
• B、
  [8](javascript:void(0);)
• C、
  [6](javascript:void(0);)
• D、
  [7](javascript:void(0);)
  A。这题不会

66

下列关键字序列中，() 是堆。（0.7 分）

• A、
  [16,23,53,31,94,72](javascript:void(0);)
• B、
  [16,72,31,23,94,53](javascript:void(0);)
• C、
  [94,23,31,72,16,53](javascript:void(0);)
• D、
  [16,53,23,94，31,72](javascript:void(0);)
  A。这题硬看

69

已知一个链表中有 3000 个结点，每个结点存放一个整数，（）可用于解决这 3000 个整数的排序问题且不需要对算法作大的变动。

（0.7 分）

• A、
  [简单选择排序方法](javascript:void(0);)
• B、
  [堆排序方法](javascript:void(0);)
• C、
  [直接插入排序法](javascript:void(0);)
• D、
  [快速排序方法](javascript:void(0);)
  D。我猜，其实我觉得只有堆排序不行，因为他要随机读取，链表太慢了

71

从时间上看，快速排序的平均性能好于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归，若每趟快速排序都将记录序列均匀地分割成为长度相接近的两个子序列，则栈的最大深度（含最外层也进栈）为

；在最坏的情况下，栈的深度为（）。

（0.7 分）

• A、
  [O（n）](javascript:void(0);)
• B、
  
• C、
  
• D、
  

A。这个题写的非常好

75

从时间上看，快速排序的平均性能好于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归，若每趟快速排序都将记录序列均匀地分割成为长度相接近的两个子序列，则栈的最大深度（含最外层也进栈）为（）。

（0.7 分）

• A、
  [O（n）](javascript:void(0);)
• B、
  
• C、
  
• D、
  

D。上个题说是 D。栈的第一层是有 n 个组那个，相当于二叉树最后一层有 n 个结点，二叉树高度至少为__。我个人认为是 logn 上取整 +1，但是百度答案是 logn 下取整 +1

百度原题：从时间上看，快速排序的平均性能好于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归，若每一趟快速排序都将记录序列均匀地分割成长度相接近的两个序列，则栈的最大深度（含最外层也进栈）为＿＿log2n 下取整 +1＿＿＿＿；在最坏情况下，栈的深度为＿＿＿n＿＿＿；如果每次先对较短的子序列进行快速排序，则栈的最大深度降为＿＿＿log2n＿＿＿；所需要的附加空间为＿＿＿log2n＿＿＿。

76

快速排序在（）情况下最不利于发挥其长处。（0.7 分）

• A、
  [被排序的数据中最大值与最小值相差不大](javascript:void(0);)
• B、
  [被排序的数据已基本有序](javascript:void(0);)
• C、
  [被排序的数据完全无序](javascript:void(0);)
• D、
  [被排序的数据量很大](javascript:void(0);)

A。我只能选 A 了，不知道选什么

79

在堆排序过程中，由 n 个待排序的记录建成初始堆需要（）次筛选；

（0.7 分）

• A、
  [n](javascript:void(0);)
• B、
  [n-1](javascript:void(0);)
• C、
  [n/2](javascript:void(0);)
• D、
  

A。不知道要几次，什么是堆排序的筛选

81

当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（）

（0.7 分）

• A、
  [n-1](javascript:void(0);)
• B、
  
• C、
  
• D、
  

A。不确定

83

对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的交换的次数为 ()

（0.7 分）

• A、
  [6](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [4](javascript:void(0);)
• D、
  [9](javascript:void(0);)
  A。这题大概是错了，从后面开始换应该是 8 次，只有从前面换才是 6 次

84

在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较（）次。（0.7 分）

• A、
  [4](javascript:void(0);)
• B、
  [2](javascript:void(0);)
• C、
  [5](javascript:void(0);)
• D、
  [3](javascript:void(0);)
  D。应该 3 次，从后往前比较

88

大多数排序算法都有两个基本的操作：（）。（0.7 分）

• A、
  [比较和交换](javascript:void(0);)
• B、
  [计算和移动](javascript:void(0);)
• C、
  [比较和移动](javascript:void(0);)
• D、
  [计算和比较](javascript:void(0);)
  C。比较和交换、比较和移动有什么区别吗

90

在对一组记录（50，40，95，20，15，70，60，45）进行冒泡排序时，在整个排序过程中共需进行 () 趟才可完成。（0.7 分）

• A、
  [6](javascript:void(0);)
• B、
  [9](javascript:void(0);)
• C、
  [8](javascript:void(0);)
• D、
  [7](javascript:void(0);)
• D。
  从后开始：

50，40，95，20，15，70，60，45

15、50、40、95、20、45、70、60——1

15、20、50、40、95、45、60、70——2

15、20、40、50、45、95、60、70——3

15、20、40、45、50、60、95、70——4

从前开始：

50，40，95，20，15，70，60，45

40、50、20、15、70、60、45、95——1

40、20、15、50、60、45、70、95——2

20、15、40、50、45、60、70、95——3

15、20、40、45、50、60、70、95——4

这题可能问的是非改进版本，应该是 n-1=7 躺

91

（）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。（0.7 分）

• A、
  [归并排序](javascript:void(0);)
• B、
  [选择排序](javascript:void(0);)
• C、
  [插入排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  B。选择排序

92

在对 n 个元素进行冒泡排序的过程中，至少需要（）趟排序完成。（0.7 分）

• A、
  [1](javascript:void(0);)
• B、
  [n/2](javascript:void(0);)
• C、
  [n](javascript:void(0);)
• D、
  [n-1](javascript:void(0);)
  A。这题脑瘫吧，哪种算法？

93

在文件局部有序或文件长度较小的情况下，最佳的排序方法是（）。

（0.7 分）

• A、
  [直接插入排序](javascript:void(0);)
• B、
  [冒泡排序](javascript:void(0);)
• C、
  [直接选择排序](javascript:void(0);)
• D、
  [归并排序](javascript:void(0);)
  A。局部有序或长度较小

94

在对 n 个元素进行直接插入排序的过程中，共需要进行（）趟。（0.7 分）

• A、
  [2n](javascript:void(0);)
• B、
  [n-1](javascript:void(0);)
• C、
  [n](javascript:void(0);)
• D、
  [n+1](javascript:void(0);)
  B，插入、选择都是 n-1 趟

96

若对 n 个元素进行归并排序，则进行每一趟归并的时间复杂度为（）

（0.7 分）

• A、
  
• B、
  [O(n)](javascript:void(0);)
• C、
  
• D、
  [O(1)](javascript:void(0);)
  B。因为归并 logn 次

102

设有序表中有 1000 个元素，则用二分查找查找元素 X 最多需要比较（）次。（0.7 分）

• A、
  [1](javascript:void(0);)
• B、
  [10](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [25](javascript:void(0);)
  B。2^10-1=1023

103

在堆排序中、快速排序和归并排序中，若只从平均情况下排序的速度来考虑，应选用（）方法。

（0.7 分）

• A、
  [归并排序](javascript:void(0);)
• B、
  [堆排序](javascript:void(0);)
• C、
  [都是一样的，选哪种排序方法都可以](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  D。好像是快速排序吧

105

设一组初始记录关键字的长度为 8，则最多经过（）趟插入排序可以得到有序序列。（0.7 分）

• A、
  [8](javascript:void(0);)
• B、
  [6](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [9](javascript:void(0);)
  C。插入和选择应该都是 n-1

108

从时间上看，快速排序的平均性能好于其他排序方法，但从空间上看，快速排序需要一个栈空间来实现递归，若每趟快速排序都将记录序列均匀地分割成为长度相接近的两个子序列，则栈的最大深度（含最外层也进栈）为

；如果每次先对较短的子序列进行快速排序，所需要的附加空间为（）。

（0.7 分）

• A、
  [O（n）](javascript:void(0);)
• B、
  
• C、
  
• D、
  [log2n+1](javascript:void(0);)
  A。如果一直屯着，每次都找最小值，那深度就是 N

112

在对一组记录（50，40，95，20，15，70，60，45，80）进行直接选择排序时，第 4 次交换和选择后，未排序记录（即无序表）为 ()。（0.7 分）

• A、
  [(45,70,60,95,80)](javascript:void(0);)
• B、
  [(50,70,60,95,80)](javascript:void(0);)
• C、
  [(50,40,60,95,80)](javascript:void(0);)
• D、
  [(20,70,60,95,80)](javascript:void(0);)
  B。这题还有点麻烦

113

设一组初始记录关键字序列为 (345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。（0.7 分）

• A、
  [8](javascript:void(0);)
• B、
  [5](javascript:void(0);)
• C、
  [3](javascript:void(0);)
• D、
  [4](javascript:void(0);)
  C。三位数就是三趟

115

设关键字序列为：3，7，6，9，8，1，4，5，2.用选择排序，进行排序的交换次数是（）。（0.7 分）

• A、
  [5](javascript:void(0);)
• B、
  [7](javascript:void(0);)
• C、
  [6](javascript:void(0);)
• D、
  [4](javascript:void(0);)
  C。这题好恶心

176983452——1 次

126983457——2 次

123986457——3 次

123486957——4 次

123456987——5 次

123456987——5 次

123456789——6 次

118

如果将所有中国人按照生日来排序，则使用（）算法最快。

（0.7 分）

• A、
  [归并排序](javascript:void(0);)
• B、
  [快速排序](javascript:void(0);)
• C、
  [基数排序](javascript:void(0);)
• D、
  [希尔排序](javascript:void(0);)
  C。我猜的

119

以下说法错误的是 ()（0.7 分）

• A、
  [线性结构中的一个结点至多只有一个直接后继](javascript:void(0);)
• B、
  [树形结构可以表达(组织)更复杂的数据](javascript:void(0);)
• C、
  [树形结构的特点是一个结点可以有多个直接前趋](javascript:void(0);)
• D、
  [任何只含一个结点的集合是一棵树](javascript:void(0);)
  B。注意 D，树和二叉树都可以为空

123

在堆排序过程中，由初始堆到堆排序结束需要进行（）次筛选。

（0.7 分）

• A、
  
• B、
  [n](javascript:void(0);)
• C、
  [n-1](javascript:void(0);)
• D、
  [n/2](javascript:void(0);)
  C。形成大顶堆要 n/2 下取整次筛选；之后每拿走一个最大值要筛选一次维护堆，维护堆要 n-1 次。

124

设一组记录关键字序列为 (49,38,65,97,76,13,27,49*)，建立小数堆，第一次调整结束后（）按从上到下从左到右的顺序依次读取结点，其顺序为（）。

（0.7 分）

• A、
  [（97，38,49,49*，76,65,27,13）](javascript:void(0);)
• B、
  [（13，38,27，49*，76,65,49,97）](javascript:void(0);)
• C、
  [（13，38,49,49*，27,65,76,97）](javascript:void(0);)
• D、
  [（13，27,38,49,49*，65，76,97）](javascript:void(0);)
  什么交第一次调整结束？我就认为是建堆结束

126

一般情况下，以下四种排序方法中，平均查找长度最小的是（）

（0.7 分）

• A、
  [插入排序](javascript:void(0);)
• B、
  [选择排序](javascript:void(0);)
• C、
  [快速排序](javascript:void(0);)
• D、
  [归并排序](javascript:void(0);)
  C。排序是排序，查找是查找，你再说尼玛呢？

127

在内部排序中，平均比较次数最少的是 ()。

（0.7 分）

• A、
  [shell排序](javascript:void(0);)
• B、
  [归并排序](javascript:void(0);)
• C、
  [快速排序](javascript:void(0);)
• D、
  [选择排序](javascript:void(0);)
  C。我不会，比较次数多少怎么算哦

128

设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用（）排序法。

（0.7 分）

• A、
  [冒泡排序](javascript:void(0);)
• B、
  [基数排序](javascript:void(0);)
• C、
  [堆排序](javascript:void(0);)
• D、
  [快速排序](javascript:void(0);)
  A。冒泡冒 10 次，复杂度 On，但是 log1000 也就是 10

133

设一组初始关键字序列为 (38，65，97，76，13，27，10)，对该序列进行升序排序，则第 3 趟冒泡排序结束后的结果为 ()。（0.7 分）

• A、
  [(38，13，27，10，65，76，97)](javascript:void(0);)
• B、
  [(10，13，27，76，65，97，38)](javascript:void(0);)
• C、
  [(65，13，27，10，38，76，97)](javascript:void(0);)
• D、
  [(13，38，27，10，65，76，97)](javascript:void(0);)
  A。从后面开始冒泡的

从后面开始冒泡：

10、38、65、97、76、13、27——1

10、13、38、65、97、76、27——2

10、13、27、65、97、76、38——3

从前面开始冒泡：

38、65、76、13、27、10、97——1

38、65、13、27、10、76、97——2

38、13、27、10、65、76、97——3

135

对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，在整个排序过程中最多需要进行 () 趟排序才可以完成。（0.7 分）

• A、
  [9](javascript:void(0);)
• B、
  [6](javascript:void(0);)
• C、
  [7](javascript:void(0);)
• D、
  [8](javascript:void(0);)
  D。就是 n-1 躺，插入、选择都是 n-1

136

将 5 个不同的数据进行排序，至多需要比较（）次。

（0.7 分）

• A、
  [25](javascript:void(0);)
• B、
  [8](javascript:void(0);)
• C、
  [9](javascript:void(0);)
• D、
  [10](javascript:void(0);)
  D。我的做法是 4*5/2，任意两个数据都比一次

137

在直接插入和直接选择排序中，若初始数据基本反序，则选用 ()。

（0.7 分）

• A、
  [先直接插入然后直接选择排序](javascript:void(0);)
• B、
  [直接插入排序](javascript:void(0);)
• C、
  [先直接选择排序然后直接插入排序](javascript:void(0);)
• D、
  [直接选择排序](javascript:void(0);)
  D。这不是只能选一种吗？

138

假定一组记录为（46，79，56，64，38，40，84，43），在冒泡排序的过程中进行第一趟排序时，元素 79 将最终下沉到其后第 () 个元素的位置。（0.7 分）

• A、
  [4](javascript:void(0);)
• B、
  [6](javascript:void(0);)
• C、
  [3](javascript:void(0);)
• D、
  [5](javascript:void(0);)
  B。你问的是下沉，我就当你从第一个开始

139

一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。

（0.7 分）

• A、
  [希尔排序](javascript:void(0);)
• B、
  [快速排序](javascript:void(0);)
• C、
  [冒泡排序](javascript:void(0);)
• D、
  [堆排序](javascript:void(0);)
  B。我觉得 A、D 都不能，只有 C 能